import java.util.*;

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    boolean[] visit;
    public int combinationSum4(int[] nums, int target) {
        //这道题完全可以用回溯算法来写
        //注意这道题不是组合，而是排列问题
        //排序
        Arrays.sort(nums);
        visit = new boolean[nums.length];
        backTracking(nums, target);
        return ret.size();
    }

    private void backTracking(int[] nums, int target) {
        int sum = 0;
        for (int x : path) {
            sum += x;
        }

        if (sum == target) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visit[i]) {
                continue;
            }
            path.add(nums[i]);
            backTracking(nums, target);
            path.remove(path.size() - 1);
            visit[i] = false;
        }

    }
}

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public static void main(String[] args) {
        StringBuilder str = new StringBuilder();
        str.append(1);
        System.out.println(str.toString());

        int[] quality = {3,1,10,10,1};
        int[] wage = {4,8,2,2,7};
        
        int n = quality.length;
        Integer[] h = new Integer[n];
        for (int i = 0; i < n; i++) {
            h[i] = i;
        }
        
        Arrays.sort(h, (a, b) -> {
            return quality[b] * wage[a] - quality[a] * wage[b];
        });

        for (int i = 0; i < 5; i++) {
            System.out.println(h);
        }

        Integer[] ret = new Integer[5];
        for (int i = 0; i < 5; i++) {
            ret[i] = i;
        }

    }
    public static void main8(String[] args) {

        List<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(1);
        list.add(3);
        Arrays.sort(list.toArray());
        Collections.sort(list);
        System.out.println(list);
        System.out.println(list.get(0));
        System.out.println("haha");
        System.out.println("学了linux真的");

    }
    public static void main7(String[] args) {
        int a = -333;
        int[][] nums = new int[3][2];
        System.out.println(nums.length);
        System.out.println(nums[0].length);
        System.out.println(Integer.toString(a).length());

    }
    public static void main6(String[] args) {
        int[] aa = new int[] {1, 2};
        System.out.println(aa.length);
        List<int[]> ha = new ArrayList<>();
        ha.add(new int[] {1, 2});
        ha.add(new int[] {3, 4});
        for(int[] tmp : ha) {
            for (int x : tmp) {
                System.out.print(x + " ");
            }
        }

        System.out.println();
        System.out.println(ha.size());
    }
    public static void main5(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.putIfAbsent(1,"ab");
        //通过键获取值
        Set<Character> set = new HashSet<>();
        set.add('a');
        set.contains('a');
        System.out.println(map.get(1));
    }
    public static void main4(String[] args) {
        int[] nums = {1,2,3};
        int target = 6;
        combinationSum4(nums, target);
    }
    public static int combinationSum4(int[] nums, int target) {
        //看了很多题解，感觉每个人写的都是一个框架，都是对自己而言是最好的
        //希望这个题解帮助到你
        //这道题确实是爬楼梯的最终进阶版
        //我们先忽略什么背包问题
        //我们要想到达最终的是第几级台阶
        //是 target 这级台阶
        int[] dp = new int[target + 1];
        dp[0] = 1;//这个初始化就是跳0级台阶只有一种走法
        //不要争辩，要不然没法写了各位

        //之后就可以从第一级台阶开始遍历
        for (int i = 1; i <= target; i++) {
            //此时我们nums中就相当于每次能跳多少级
            //毫无疑问，只有当台阶数大于能走的步数时才作数
            //所以此时我们遍历每次能走的台阶数
            for (int j = 0; j < nums.length; j++) {
                //当台阶数大于能走的步数时我们进行累加
                //相当于有多少种方法走到当前 i 的台阶上
                if (nums[j] <= i) {
                    dp[i] = dp[i] + dp[i - nums[j]];
                    //好，看到这里你可能去看别的题解了
                    //又蒙了,我们写爬楼梯时dp[i] = dp[i - 1] + dp[i - 2]
                    //因为每次只能走一步或者两步
                    //但是这题是每次走的步数不是固定的，所以我们要把当前值记录并累加
                }
            }
        }

        for (int x : dp) {
            System.out.print(x + " ");
        }

        //最后返回dp[target]
        //一定搞懂dp[j] 的含义
        return dp[target];
    }
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[] weigth = new int[n];
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            weigth[i] = scanner.nextInt();
            value[i] = scanner.nextInt();
        }

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j >= weigth[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weigth[i - 1]] + value[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.print(dp[n][m]);
    }
    public static void main1(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,3};
        int target = 4;
        System.out.println(solution.combinationSum4(nums, target));
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        Math.max(1,2);
    }

}